<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <!-- 10.正则表达式匹配
        给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

        '.' 匹配任意单个字符
        '*' 匹配零个或多个前面的那一个元素
        所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

         
        示例 1：

        输入：s = "aa", p = "a"
        输出：false
        解释："a" 无法匹配 "aa" 整个字符串。
        示例 2:

        输入：s = "aa", p = "a*"
        输出：true
        解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
        示例 3：

        输入：s = "ab", p = ".*"
        输出：true
        解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
     -->
    <script>
        var isMatch = function (s, p) {
            // let str = new RegExp('^' + p + '$').test(s)
            // console.log(str)

            // ---------------------------
            let i = s.length - 1;
            let j = p.length - 1;

            function match(i, j) {
                if (i < 0) {
                    while (p[j] == '*') {
                        j -= 2;
                    }
                    if (j < 0) {
                        return true
                    } else {
                        return false
                    }
                } else if (j < 0) {
                    return false
                }
                if (s[i] == p[j] || p[j] == '.') {
                    return match(i - 1, j - 1)
                } else if (p[j] == '*' && (p[j - 1] == '.' || p[j - 1] == s[i])) {
                    return match(i - 1, j) || match(i - 1, j - 2) || match(i, j - 2)
                } else if (p[j] == '*' && (p[j - 1] != '.' || p[j - 1] != s[i])) {
                    return match(i, j - 2)
                } else {
                    return false
                }
            }
            return match(i, j)
        };
        isMatch("aa", "a")
        isMatch("aa", "a*")
        isMatch("aa", ".*")
    </script>
</body>

</html>